package pers.qianyu.month_202012.date_20201215;

import org.junit.*;
import pers.qianyu.util.*;

import java.util.*;

/**
 * 322. 零钱兑换
 * https://leetcode-cn.com/problems/coin-change/
 *
 * @author mizzle rain
 * @date 2020-12-15 16:25
 */
public class CoinChange {
    // 转换为背包问题解法
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int coin : coins) {
            for (int i = 0; i <= amount; i++) {
                if (i - coin >= 0)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
            ArrayUtil.printArrayAsMarkdownTable(coin, dp);
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

    @Test
    public void test1() {
        int[] coins = {1, 2, 5};
        int amount = 11;
        int result = new CoinChange().coinChange(coins, amount);
        System.out.println("result = " + result);
    }
}
